The simulation of a stochastic process, whose outcome is probabilistic in nature, requires the use of a random, or pseudo-random, number. Hereinafter, the term “random number” will be used to denote both a truly random number and a pseudo random number. A statistical computing system such as a stochastic neural network requires a large number (e.g., thousands) of random numbers. When multiple random numbers were required to be independent, separate random number generators were employed, often requiring different algorithms for each random number generator. Presently, integrated circuits perform mathematical operations for a system. Integrating large numbers of random number generators onto an integrated circuit is inefficient and costly at best and impossible at worst. In addition, separate random number generators may only produce one random bit per clock cycle. There is a need for a device and method that generates multiple random bit sequences, where multiple bits are produced per clock cycle, that is simple to design and easily expanded to add additional random bit sequences.
In an article by Joshua Alspector, et al., entitled “A VLSI-efficient technique for generating multiple uncorrelated noise sources and its application to stochastic neural networks,” IEEE Transactions On Circuits and Systems, January 1991, Vol. 38, No. 1, pp. 109-123, a method is disclosed of generating multiple bit sequences from a single pseudo-random bit generator by tapping a shift register of the pseudo-random bit generator. Specifically, three taps are made for each random bit sequence required, where each set of taps is modulo 2 added to produce a time-shifted version of the random sequence produced by the pseudo-random bit generator. Different combinations of taps produce different time-shifts of the random sequence of the pseudo-random bit generator. The amount of time-shifting between sequences must be sufficient to consider the sequences uncorrelated. One drawback to this method is that the pseudo-random bit generator must be sufficiently large to allow for sufficiently different time-shifts to be selected so that the results are uncorrelated. In addition, there remains difficulty in routing unique combinations of taps on an integrated circuit, computing time-shifts for each sequence, and having to design a new time shift whenever a new sequence is required.
U.S. Pat. No. 5,251,165, entitled “TWO PHASE RANDOM NUMBER GENERATOR,” discloses a device for and method of generating a random number by generating a first random number in a first phase and then using this first random number to generate two more random numbers in a second phase. One of the two random numbers generated in the second phase is selected, based on a bit value in the random number generated in the first phase. The present invention does not use such a method. U.S. Pat. No. 5,251,165 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,793,657, entitled “RANDOM NUMBER GENERATING APPARATUS AND RANDOM NUMBER GENERATING METHOD IN A MULTIPROCESSOR SYSTEM,” discloses a device for and method of generating a random number in a multiprocessor system that allows for the number of processors to change. It does so by setting an initial value in each processor in the system from which each processor generates a random number. The random numbers then make a sequence of random numbers. If a processor is added to the system, all of the processors are reset, initial values are set in the processors, the processors generate random numbers, and the random numbers are used as a sequence of random numbers. The present invention does not use such a method. U.S. Pat. No. 5,793,657 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 6,253,223, entitled “ROBUST RANDOM NUMBER GENERATOR,” discloses a device for and method of generating a random number by producing a first random number from an analog random number generator, producing a pseudo-random number from a digital random number generator, and combining the two random numbers to produce a final random number. The present invention does not use such a method. U.S. Pat. No. 6,253,223 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 6,480,870, entitled “RANDOM NUMBER GENERATOR USING LEHMER ALGORITHM,” discloses a device for and method of generating a random number by using a plurality of bit generators to produce a plurality of sum bits and a plurality of carry bits. The carry bits are converted to a three-bit number which is then added to the sum bits to produce a random number. The present invention does not use such a method. U.S. Pat. No. 6,480,870 is hereby incorporated by reference into the specification of the present invention.